package algorithms.a02sortbasic;

import algorithms.beans.Student;
import algorithms.utis.AlgorithmsUtis;
import algorithms.utis.SortTestHelper;

import java.util.Arrays;

public class SelectionSort {

    // 我们的算法类不允许产生任何实例
    private SelectionSort() {
    }

    /**
     * 1,整型数组排序
     *
     * @param arr
     * @date: 2018-02-04 下午 6:22
     * @author: 王昊然
     */
    public static void sort(int[] arr) {

        int n = arr.length;

        //第一层循环，选择当前要处理的数字位置
        for (int i = 0; i < n - 1; i++) { //这里其实严格来讲用i<n-1即可，课程中用的i<n

            // 第二层循环，寻找[i, n)区间里的最小值，替换到i的位置
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }

            AlgorithmsUtis.swap(arr, i, minIndex);
        }
    }

    public static void sort(Comparable[] arr) {

        int n = arr.length;

        //第一层循环，选择当前要处理的数字位置
        for (int i = 0; i < n - 1; i++) { //这里其实严格来讲用i<n-1即可，课程中用的i<n

            // 第二层循环，寻找[i, n)区间里的最小值，替换到i的位置
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0)
                    minIndex = j;
            }

            AlgorithmsUtis.swap(arr, i, minIndex);
        }
    }


    /**
     * 优化算法
     * 上面的基本算法是找最小值，其实可以最大值和最小值一起处理
     *
     * @param arr
     * @date: 2018/2/5 10:07
     * @author: 王昊然
     */
    public static void sortWithMinAndMax(Comparable[] arr) {

        int n = arr.length;

        //1先确定最左和最右两个位置，并保证最左的值小于最右
        int left = 0;
        int right = n - 1;

        while (left < right) {

            if (arr[left].compareTo(arr[right]) > 0) {
                AlgorithmsUtis.swap(arr, left, right);
            }

            int minIndex = left;
            int maxIndex = right;

            for (int i = left + 1; i < right; i++) {
                if (arr[i].compareTo(arr[minIndex]) < 0)
                    minIndex = i;
                else if (arr[i].compareTo(arr[maxIndex]) > 0)
                    maxIndex = i;
            }

            AlgorithmsUtis.swap(arr, left, minIndex);
            AlgorithmsUtis.swap(arr, right, maxIndex);

            left++;
            right--;
        }
    }


    public static void main(String[] args) {

//        testIntArr();
//        testDoubleArr();
//        testStringArr();
//        testStudentArr();

        testSort();
    }


    /**
     * 测试int
     *
     * @date: 2018-02-04 下午 10:16
     * @author: 王昊然
     */
    private static void testIntArr() {

        Integer[] a = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        SelectionSort.sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
            System.out.print(' ');
        }
        System.out.println();
    }

    /**
     * 测试Double
     *
     * @date: 2018-02-04 下午 10:16
     * @author: 王昊然
     */
    private static void testDoubleArr() {

        Double[] b = {4.4, 3.3, 2.2, 1.1};
        SelectionSort.sort(b);
        for (int i = 0; i < b.length; i++) {
            System.out.print(b[i]);
            System.out.print(' ');
        }
        System.out.println();
    }

    /**
     * 测试String
     *
     * @date: 2018-02-04 下午 10:16
     * @author: 王昊然
     */
    private static void testStringArr() {

        String[] c = {"D", "C", "B", "A"};
        SelectionSort.sort(c);
        for (int i = 0; i < c.length; i++) {
            System.out.print(c[i]);
            System.out.print(' ');
        }
        System.out.println();
    }

    /**
     * 测试自定义Student类
     *
     * @date: 2018-02-04 下午 10:19
     * @author: 王昊然
     */
    private static void testStudentArr() {
        Student[] d = new Student[4];
        d[0] = new Student("D", 90);
        d[1] = new Student("C", 100);
        d[2] = new Student("B", 95);
        d[3] = new Student("A", 95);
        SelectionSort.sort(d);
        for (int i = 0; i < d.length; i++)
            System.out.println(d[i]);
    }


    /**
     * 测试排序算法辅助函数
     *
     * @date: 2018-02-04 下午 10:22
     * @author: 王昊然
     */
    private static void testSort() {

        // 测试排序算法辅助函数
        int N = 3000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 1000000);
        Integer[] arr1 = Arrays.copyOf(arr, arr.length);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);

        System.out.print("忽略------");
        SortTestHelper.testSort(SelectionSort.class, arr);
        SortTestHelper.testSort(SelectionSort.class, arr1,"sortWithMinAndMax");
        System.out.println();

        SortTestHelper.testSort(SelectionSort.class, arr2);
        SortTestHelper.testSort(SelectionSort.class, arr3, "sortWithMinAndMax");
    }
}
